package maze;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * 用队列的方法求解迷宫问题，该方法得到的路径必然是一条最短的可行路径
 * 这种方法是将迷宫问题看做一个图结构，每一个可行的位置都是图上的一个顶点，
 * 相邻两个可行位置就组成一条边，用队列的方法求解迷宫问题就相当于用广度优先算法
 * 来遍历图，区别就是这里只要遍历到终点位置就退出了
 *
 * @author zj
 */
public class QueueMethod {
    public static void main(String[] args) {
        maze(1, 1, 10, 10);
    }

    private static void maze(int startI, int startJ, int endI, int endJ) {
        Global.print(Global.M);
        int i = -1, j = -1;
        ArrayList<QueuePos> list = new ArrayList<QueuePos>(); //保存所有出过队列的位置
        //用LinkedList来维持一个队列，从队尾添加，从队头删除
        LinkedList<QueuePos> queue = new LinkedList<QueuePos>();
        QueuePos startPos = new QueuePos(startI, startJ, null);
        queue.addLast(startPos);

        Global.M[startI][startJ] = -1; //设置为-1表示已经入过队列

        while (!queue.isEmpty()) {
            QueuePos head = queue.removeFirst();
            if (head.i == endI && head.j == endJ) {
                System.out.println("找到一条最短可行路径");

                //把所有扫描过的可通过的位置的值重置为0
                if (list != null) {
                    for (int h = 0; h < list.size(); h++) {
                        Global.M[list.get(h).i][list.get(h).j] = 0;
                    }
                }
                if (queue != null) {
                    for (int h = 0; h < queue.size(); h++) {
                        Global.M[queue.get(h).i][queue.get(h).j] = 0;
                    }
                }

                //从终点开始，一直往前寻找前一步路径，直到起点，将路径上的位置的值设置为-1，以便打印时区别
                QueuePos q = head;
                while (q != null) {
                    System.out.print("(" + q.i + "," + q.j + ") ");
                    Global.M[q.i][q.j] = -1;
                    q = q.front;
                }
                System.out.println();
                Global.print(Global.M);
                return;
            } else { //如果不是终点，就把该位置加入队列中
                list.add(head);

                //同时，遍历东南西北四个方向，把可行位置都加入队列中
                i = head.i;
                j = head.j + 1;
                if (Global.M[i][j] == 0) {
                    queue.addLast(new QueuePos(i, j, head));
                    Global.M[i][j] = -1;
                }

                i = head.i - 1;
                j = head.j;
                if (Global.M[i][j] == 0) {
                    queue.addLast(new QueuePos(i, j, head));
                    Global.M[i][j] = -1;
                }

                i = head.i;
                j = head.j - 1;
                if (Global.M[i][j] == 0) {
                    queue.addLast(new QueuePos(i, j, head));
                    Global.M[i][j] = -1;
                }

                i = head.i + 1;
                j = head.j;
                if (Global.M[i][j] == 0) {
                    queue.addLast(new QueuePos(i, j, head));
                    Global.M[i][j] = -1;
                }
            }
        }
    }
}
